package ljl.alg.hot100;

import commons.ListNode;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

public class _160_intersection_node {
    
    /*
    * 先来个移花接木，接一块
    * 这个叫双指针
    * */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        ListNode p1 = headA, p2= headB;
        while (p1 != p2) {
            if (p1 == null) p1 = headB;
            else p1 = p1.next;
            if (p2 == null) p2 = headA;
            else p2 = p2.next;
        }
        return p1;
    }
    
    /*
    * 不用两个栈，有点笨逼，用一个 set 就行了
    * */
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        Set<ListNode> set = new HashSet<>();
        while (headA != null) {
            set.add(headA);
            headA = headA.next;
        }
        while (headB != null) {
            if (set.contains(headB))
                return headB;
            headB = headB.next;
        }
        return null;
    }
    
    /*
    * 我的笨逼解法也写写
    * 确实有点慢
    * */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        LinkedList<ListNode> stack1 = new LinkedList<>();
        LinkedList<ListNode> stack2 = new LinkedList<>();
        
        while (headA != null) {
            stack1.push(headA);
            headA = headA.next;
        }
        while (headB != null) {
            stack2.push(headB);
            headB = headB.next;
        }
        ListNode res = null;
        while (!stack1.isEmpty() && !stack2.isEmpty() && stack1.peek() == stack2.peek()) {
            res = stack1.peek();
            stack1.pop();
            stack2.pop();
        }
        return res;
    }
}
